package com.shawn.datastructure.linkedlist;

public class SinglyLinkedList {

	private Node head;

	public Node findByValue(int value) {
		Node p = head;
		while (p != null && p.data != value) {
			p = p.next;
		}
		return p;
	}

	public Node findByIndex(int index) {
		Node p = head;
		int pos = 0;
		while (p != null && pos != index) {
			p = p.next;
			pos++;
		}
		return p;
	}

	public void insertToHead(int value) {
		Node newNode = new Node(value, null);
		insertToHead(newNode);
	}

	public void insertToHead(Node node) {
		if (head == null) {
			head = node;
			return;
		}
		node.next = head;
		head = node;
	}

	public void insertToTail(int value) {
		Node newNode = new Node(value, null);
		insertToTail(newNode);
	}

	public void insertToTail(Node node) {
		if (head == null) {
			head = node;
			return;
		}
		Node p = head;
		while (p.next != null) {
			p = p.next;
		}
		p.next = node;
	}

	public void insertAfter(Node node, int value) {
		insertAfter(node, new Node(value, null));
	}

	public void insertAfter(Node node, Node newNode) {
		if (node == null) {
			return;
		}
		newNode.next = node.next;
		node.next = newNode;
	}

	public void insertBefore(Node node, int value) {
		insertBefore(node, new Node(value, null));
	}

	public void insertBefore(Node node, Node newNode) {
		if (node == null) {
			return;
		}
		if (node == head) {
			insertToHead(newNode);
			return;
		}
		Node p = head;
		while (p != null && p.next != node) {
			p = p.next;
		}
		if (p == null) {
			return;
		}
		newNode.next = p.next;
		p.next = newNode;
	}

	public void deleteByValue(int value) {
		if (head == null) {
			return;
		}
		Node p = head;
		Node q = null;
		while (p != null && p.data != value) {
			q = p;
			p = p.next;
		}
		if (p == null) {
			return;
		}
		if (q == null) {
			head = head.next;
		} else {
			q.next = q.next.next;
		}
	}

	// 可重复删除相同值的节点
	public void loopDeleteByValue(int value) {
		if (head == null) {
			return;
		}
		if (head != null && head.data == value) {
			head = head.next;
		}
		Node p = head;
		while (p != null) {
			if (p.next.data == value) {
				p.next = p.next.next;
				continue;
			}
			p = p.next;
		}
	}

	public void deleteByNode(Node node) {
		if (node == null || head == null) {
			return;
		}
		if (node == head) {
			head = head.next;
			return;
		}

		Node p = head;
		while (p != null && p.next != node) {
			p = p.next;
		}

		if (p == null) {
			return;
		}
		p.next = p.next.next;
	}

	private static class Node {

		int data;
		Node next;

		Node(int data, Node next) {
			this.data = data;
			this.next = next;
		}
	}

}
